package simple;

import data.TreeNode;

import java.util.Stack;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/8/1 19:18
 */
public class No226_翻转二叉树 {
    public static void main(String[] args) {
        Solution226 solution226 = new Solution226();
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);
        TreeNode treeNode = solution226.invertTree(root);
        System.out.println(treeNode);
    }
}

class Solution226 {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        //迭代法:广度优先搜索 BFS
        //参考视频No107_2_1
        //初始化
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        //开始迭代
        while (!stack.isEmpty()) {
            //当前节点
            TreeNode check = stack.pop();
            if (check.left == null && check.right == null) {
                continue;
            }
            //开始交换左右子树
            TreeNode tmp = check.left;
            check.left = check.right;
            check.right = tmp;
            if (check.left != null) {
                stack.push(check.left);
            }
            if (check.right != null) {
                stack.push(check.right);
            }
        }
        return root;
    }
}



    //public TreeNode invertTree(TreeNode root) {
    //    //递归,深度优先搜索DFS
    //    //递归结束条件
    //    if (root == null || (root.left == null && root.right == null)) {
    //        return root;
    //    }
    //    //获取当前节点root的左右子树
    //    TreeNode left = root.left;
    //    TreeNode right = root.right;
    //    //定义交换变量
    //    TreeNode tmp = left;
    //    left = right;
    //    right = tmp;
    //    //这时候左右子树已经交换
    //    root.left = left;
    //    root.right = right;
    //    //递归左右子树交换
    //    invertTree(root.left);
    //    invertTree(root.right);
    //    return root;
    //}